// https://www.lintcode.com/problem/316/?_from=collection&fromId=186
class Solution {
public:
    /**
     * @param num: a array
     * @param target: a num
     * @return: return all combinations
     */
    void getComb(vector<int> &num, vector<int> &tmp, vector<bool> &visited, int val, int target, vector<int> &res) {
        if (val > target) return; //重要，不只是剪枝，元素允许重复了，所以这句是作为递归退出条件
        if (!tmp.empty() && val < target) {
            res.push_back(val);
        }
        for (int i = 0; i < num.size(); ++i) {
            // if (visited[i]) continue; 可重复
            // visited[i] = true;
            if (!tmp.empty() && tmp[0] == 0) continue; //注意对0的处理，例如011 02
            tmp.push_back(num[i]);
            val = val * 10 + num[i];
            getComb(num, tmp, visited, val, target, res);
            tmp.pop_back();
            val /= 10;
            // visited[i] = false;
        }
    }
    vector<int> combinationSet(vector<int> &num, int target) {
        vector<int> res;
        vector<int> tmp;
        vector<bool> visited(num.size(), false);
        int val = 0;
        getComb(num, tmp, visited, val, target, res);
        return res;
    }
};


class Solution {
public:
    /**
     * @param num: a array
     * @param target: a num
     * @return: return all combinations
     *          we will sort your return value in output
     */
    void helper(int target, int val, vector<int>& tmp, vector<int> &num, vector<int>& res) {
        if (val >= target) return;
        if (!tmp.empty()) res.push_back(val);
        // for (int i = start; i < num.size(); ++i) { // 允许往前取数，组成不同的数字
        for (int i = 0; i < num.size(); ++i) {
            if (!tmp.empty() && tmp[0] == 0) continue; //注意对0的处理，例如011 02
            val = val * 10 + num[i];
            tmp.push_back(num[i]);
            helper(target, val, tmp, num, res);
            val /= 10;
            tmp.pop_back();
        }
    }
    vector<int> combinationSet(vector<int> &num, int target) {
        vector<int> res;
        vector<int> tmp;
        helper(target, 0, tmp, num, res);
        return res;
    }
};